package com.zdp.leetcodeMiddle;

import java.util.Stack;

/*
* 题目描述：
* 给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 字符串解码_394 {
    public static void main(String[] args) {
        字符串解码_394 demo = new 字符串解码_394();
        String s = "100[leetcode]";
        System.out.println(demo.decodeString(s));
    }

    /*
    * 解题思路： 利用栈结构就可以解决
    * 使用两个栈 一个存放数字 一个存放字母
    *  用一个栈也可以  数字后面永远跟着 [
    * */
    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        Stack<Integer> nums = new Stack<>();
        Stack<Character> words = new Stack<>();
        int length = s.length();
        for(int i =0;i<length;i++){
            Character t = s.charAt(i);
            if(Character.isDigit(t)){
                // 如果是数字，处理完后入栈
                Integer num = t-'0';
                while(Character.isDigit(s.charAt(i+1))){
                    // 如果后续的也是数字的话
                    i++;
                    num = s.charAt(i) - '0' + num *10;
                }
                nums.push(num);
            }else if(t == ']'){
                // 做处理
                int count = nums.pop();
                StringBuilder temp = new StringBuilder();
                while(words.peek() != '['){
                    temp.append(words.pop());
                }
                words.pop();
                for(int j=0;j<count;j++){
                    // 入栈
                    for(int k = temp.length()-1; k >=0;k--){
                        words.push(temp.charAt(k));
                    }
                }
            }else{
                // 其他字符 入栈
                words.push(t);
            }
        }
        // 取出所有字符
        while(!words.isEmpty()){
            result.append(words.pop());
        }
        return result.reverse().toString();
    }
}
